//题目:
// 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
#include<iostream>
#include<vector>

using namespace std;
//代码:
// class Solution
// {
//     vector<string> v;
// public:
//     void dfs(int n, int left_count, int right_count, string str)
//     {
//         if (str.size() == 2 * n)
//         {
//             v.push_back(str);
//             return;
//         }
//         if (left_count == right_count)
//         {
//             //只能放左括号
//             str += '(';
//             dfs(n, left_count + 1, right_count,str);
//         }
//         else if (left_count == n)
//         {
//             //左括号放满了，只能放有括号了
//             str += ')';
//             dfs(n, left_count, right_count + 1,str);
//         }
//         else
//         {
//             str += '(';
//             dfs(n, left_count + 1, right_count,str);//左括号一次
//             str.pop_back();//回溯
//             str += ')';
//             dfs(n, left_count, right_count + 1,str);//有括号一次
//         }
//     }
//     vector<string> generateParenthesis(int n)
//     {
//         dfs(n, 0, 0,string());
//         return v;
//     }
// };

class Solution
{
    vector<string> v;
    string str;
public:
    void dfs(int n, int left_count, int right_count)
    {
        if (str.size() == 2 * n)
        {
            v.push_back(str);
            return;
        }
        if (left_count == right_count)
        {
            //只能放左括号
            str += '(';
            dfs(n, left_count + 1, right_count);
        }
        else if (left_count == n)
        {
            //左括号放满了，只能放有括号了
            str += ')';
            dfs(n, left_count, right_count + 1);
        }
        else
        {
            str += '(';
            dfs(n, left_count + 1, right_count);//左括号一次
            str.pop_back();//回溯   
            str += ')';
            dfs(n, left_count, right_count + 1);//有括号一次
        }
        str.pop_back();//回溯 
    }
    vector<string> generateParenthesis(int n)
    {
        dfs(n, 0, 0);
        return v;
    }
};